package com.magupe.develop.algorithm;

/**
 *
 * @author
 */
public class Main1 {

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 7, 2, 4, 3, 1, 4, 5, 9};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    /**
     * 快速排序
     *
     * @param array
     * @param left
     * @param right
     */
    public static void quickSort(int[] array, int left, int right){
        if(left < right){
            // 设置基准数
            int temp = array[left];
            int p1 = left;
            int p2 = right;
            //
            while(p1 < p2){
                // 如果右指针小于基准数就停下来，去走左指针
                if(array[p2] < temp){
                    // 如果左指针的数大于基准数就停下来，左右指针数进行交换，然后让右指针继续走
                    if(array[p1] > temp){
                        int num = array[p1];
                        array[p1] = array[p2];
                        array[p2] = num;
                        p2 --;
                    } else {
                        p1 ++;
                    }
                } else {
                    p2 --;
                }
            }
            // 递归分治思想，left与基准数交换
            array[left] = array[p1];
            array[p1] = temp;
            // 递归左边和右边
            quickSort(array, left, p1);
            quickSort(array, p1+1, right);
        }
    }
}
